C/C++ 3D Game Tools/C-C++ 3D Game Tools.iso/tools/floormap.txt

Text File | 1997-02-25 | 11KB | 443 lines

FLOOR MAPPING INFO FILE THING:
===============================
S. Christian Flowers June 1995
Email: [e-mail]

Freely Distributed: I was feeling in a giving frame of mind

===========================================================

Ok, as per request here is info for floor mapping
I will stick to C/C++, no ASM will be explained.
To help as many people as I can, I'll try and keep it ANSI
I program in 32-Bit DOS. But the Method, outside of optimizing,
can be in 16-Bit too.

Quick Overview
===============
1. We assume 90 viewport. Speed is the reason for this

2. The basic equation used for finding the falloff rate to the
   horizon is:

   zdistance = (distance_to_screen * player_height) / screen_y_position;

3. Distance to the screen is up to you. 160,128,256..what ever you choose.
   I suggest 128 or 256 so the fall off can be done a litte faster if
   computed at runtime.

   for example: if you choose distance_to_screen to be 128

   zdistance = (player_height<<7) / screen_y_position;

4. The tile size I use is 256X256. This can easily be reduced to 64X64.
   Why 256X256? It gives a smoother result at low floor height and
   the graphic looks cleaner.

   Most programmers may be used to ANDing the value by 63 at get
   the tile value. I never liked the results useing that method.
   I choose 256 X 256 because you can do this:

   int worldcoord = 204837;
   unsigned char tileval=worldcoord;

   C will autowrap tileval with an 0-255 for you without any need
   of checking the range of worldcoord.

   Then tileval/4 or tileval>>2  will give you an 0-63 value.

   I will admit worldcoor&63 is faster but it just looks crummy
   at a low floor height. your call can do what you want.

 5. Screen assumed to be 320X200


Ok, The basic Algorithm:
========================

   int count=32000; //counts into the screen buffer the current pixel
                    //to be drawn. set to start at horizon i.e. mid screen
                    //100*320

  for(i=0;i<100; i++,count++){ //count from horizon to bottom of screen

      compute falloff or z distance for this line

      get left edge = z_dist   + Player xy
      get right edge = -z_dist + Player xy

      rotate left and right edge points

      get xspan = distance between Leftx and Rightx values
      get yspan = distance between Lefty and Righty values

      xscale=xspan/screenwidth
      yscale=yspan/screenwidth

      sx,sy begin at left edge

   for(j=0; j<screenwidth; j++){

       tilex=sx;  //force an 0-255 value
       tiley=sy;

       choose 1 of these and draw pixel at count:
       ==========================================
       1. buffer[count]=tile[(tiley*256)+tilex];    //256X256
       2. buffer[count]=tile[(tiley<<8)+tilex];     //faster 256X256
       3. buffer[count]=tile[((tiley>>2)<<6)+(tilex>>2)]; //faster 64X64

       sx+=xscale;  //step to next
       sy+=yscale;

     }

   }
  done

==================================
A INDEPTH OVERVIEW OF FLOORMAPPING
==================================

I program in 32-DOS so to avoid bugs in your code here are the data
sizes:
     char = 1 byte
     short= 2 bytes
     int  = 4 bytes

Now the player:

 int pa;        //player angle
 int ph=128;    //player height
 int px=2048;   //player start x
 int py=2048;   //player y
 int pspeed=15; //player speed of movement
 int pxv;       //player x velocity
 int pyv;       //player y velocity

Player movement is calculated as follows:

   pxv=0-pspeed*SIN(pa); //compute x & y velocities
   pyv=0+pspeed*COS(pa);
   px+=pxv;              //move the player
   py+=pyv;

Why the extra 0 in there? This is why:
if you look at the world from a topdown position
it looks like this:
                    -Y
                     |
               -X----0----+X        player at 0
                     |
                    +Y

we want the player to default faceing SOUTH i.e. +Y direction
so the view cone defaults like this:

                   -Y
                    |
                   EYE player at 0
                   /|\
                 /  |  \
               /    |    \
             /      |      \
            -----------------   SCREEN topdown
     Right -X     SOUTH     +X  Left
                   +Y

This also makes ScreenLeft +X and ScreenRight -X.
All of this has its advantages, though it may seem wierd right now.
One advantage is we always compute the floors falloff distance in
the direction of +Y so we need to default the player in that direction.

FALLOFF
=======
We look at the world topdown 2D the player faceing +Y as explained above.
There are 100 horizontal screen lines from the horizon to the bottom
of the screen. So the falloff distance refers to +Y going away from
the player. Line 1 is the horizon and line 100 is the bottom of the screen

 SIDE VIEW of calculating falloff
 ================================
          SCREEN
            |
            |
            |
            |
 EYE -------|1-----------------------------> Faceing SOUTH
  | \       |
  |   \     |
  |     \   |
  |       \ |
  |         .100  current ScreenYpos (1-100)
  |           \
  |             \
  Height----------.-------------------------
                    Falloff +Y

  Falloff=(EyetoScreen*Height)/ScreenYpos;

  Generate a lookup for Height
  ============================
  float falloffdistance[100];  //floats are converted to fixed point later
  float ScreenYpos=1.000;
  float EyetoScreen=128.000;
  float Height=playerheight;

  for(i=0;i<100;i++,ScreenYpos+=1.000){

    falloffdistance[i]=(EyetoScreen*Height)/ScreenYpos;

  }

  We begin ScreenYpos at 1 rather than 0 to avoid a divide by 0
  error that would result.

XWIDTH
======
+Y is the falloff at each horizontal line on Screen.
Left X to Right X is the X width at each +Y distance.
So, if the screen is 320 pixels wide, we just divide the X width by 320
to cut the X width into 320 equal parts then loop through them and
draw 320 pixels to the screen.

This is where the 90 degree viewport saves some effort.
If +Y equals 25600 then Left X is 25600 and Right x is -25600,
remember the players faces south so Right is -X.

                         EYE    Faceing South
                         /|\
                       /  |  \
                     /    |    \
                   /      |      \
                 /        |        \
               /          |          \
  Screen Right. ----------|------------.Screen Left
           /              |             \
         /                |               \
 Rx,Ry /.                 |                .\Lx,Ly
                       Fall off
 -X                      +Y                   +X

With these values we create a line:

  Lx=Y;  Ly=Y; //the left edge
  Rx=-Y; Ry=Y; //the right edge

Now if we wanted to map this horizontal line to the screen:

   float xstep=-((Lx-Rx)/320);
   float lx=Lx+playerx;
   unsigned char x;
   unsigned char y=Ly+playery; //or Ry doesn't matter here, but it will later

   for(i=0;i<320;i++){  //map 320 pixels at +Y

          x=lx;  //force 0-255 vaule

          screen[i]=tile[(y*256)+x]; //draw it

          lx+=xstep; //step to next
   }

In doing the above at each of the 100 ScreenY positions
You will map a non-rotated floor. But...that sucks.

Rotations
=========
 I use a 640 degree system. Everything is programmed in fixed point
 and all floats can be removed. But for this file I will explain
 useing floats. You will have to write your code in fixed point if
 you want realtime results.

 So first off we need Sine & Cosine Tables

 float SIN[640];  //global arrays
 float COS[640];

//
//Makes Sin & Cos Tables num is number of degrees
//
void maketrigtables(int num){
     int i;
     float radians=0;

     for(i=0;i<num;i++){
        COS[i]=cos(radians);
        SIN[i]=sin(radians);
        radians=6.28/num;
     }

  return;
 }

For those who don't know:
=========================
Rotating a 2d point is done as follows:

int x=10; int y=10; //original coords
int nx,ny;          //the new coords
int a=20;           //the angle of rotation 0-639

   nx=(x*COS[a])-(y*SIN[a]);
   ny=(x*SIN[a])+(y*COS[a]);

So,in knowing this we can all move to the final stages of codeing this thing

HERE GOES...THE FLOOR MAPPER
=============================
//
//  a   is the angle of rotation
//  fh  is the floor's height
//
//  all in float where needed
//
//  I'll write for a 64X64 tile
//  buffer[] is assume 64k i.e. 320X320
//
void slowmapfloor(int a,int fh){

   int count=32000;     //set pixel counter at horizon
   int i,j;             //loop counters
   float ypos=1.00;     //current ypos
   float Lx,Ly;         //Left edge end point
   float Rx,Ry;         //Right edge end point
   float fdist;         //fall off distance
   float xstep;         //to walk x values
   float ystep;         //to walk y values
   float x,y;           //current world position
   float dts=128;       //distance to screen from eye
   float fheight=fh;    //float height
   unsigned char tx,ty; //tile x and y
   float fdsin,fdcos;   //Sin and Cos values at fdist to speed up routine

   for(i=0;i<100;i++,ypos+=1.00){   //loop screen y : 100 lines

     fdist=(fheight*dts)/ypos;  //compute falloff

     //Compute and Rotate Left and Right endpoints
     fdsin=fdist*SIN[a];  //speed up the rotations a little
     fdcos=fdcos*COS[a];  //with this

     Lx=fdcos-fdsin;    //rotate Left edge
     Ly=fdsin+fdcos;

     Rx=(-fdcos)-fdsin; //rotate Right Edge
     Ry=(-fdsin)+fdcos;

     //Compute xstep and ystep
     if(Lx>Rx){ xstep=(Lx-Rx)/320; xstep=-xstep}  //xstep
      else{ xstep=(Rx-Lx)/320;}

     if(Ly>Ry){ ystep=(Ly-Ry)/320; ystep=-ystep}  //ystep
      else{ ystep=(Ry-Ly)/320;}

     x=Lx+px; y=Ly+py; //start at left edge

      for(j=0;j<320;j++,count++){ // loop screen x: 320 pixels

        tx=x; ty=y; //force 0-255 results

        buffer[count]=tile[((ty>>2)<<6)+(tx>>2)]; //draw 1 pixel

        x+=xstep; //step to the next x & y position
        y+=ystep;

      }//end j

   }//end i

 return;
}



Tadah...That's it. I hope it helps

BUT WAIT!
=========
As written it is SLOW as the government comeing forth about Aliens
Optimized and it blazes. So convert any and all floats to fixed point
would be a start. That will increase speed but not as fast as it could
be.

Hints on optimizing
====================

  pointers:  the buffer[] portion can be written better

  As written is:
  --------------
  count=32000;

  for(i=0;i<100;i++){

   for(j=0;j<320;j++,count++){

    buffer[count]=pixel;

   }

  }

  Faster:
  -------
  unsigned char *buf=buffer+32000;

  for(i=0;i<100;i++){

   for(j=0;j<320;j++,buf++){

    *(buf)=pixel;

   }

  }

 That will kill 32000 underlying additions C does when offsetting
 from the pointer when buffer[count] was used.

 There are even faster ways in 32-Bit C++ useing unions
 to allow drawing 4 pixels at once. And I don't mean MODE X.
 But I'll keep those to myself. Hey, You can't have it all for free.

 LAST WORDS:
 ============
 In case you didn't notice, You just go 100 -> 1 in the outerloop
 to map a ceiling.

 Any questions Email me [e-mail]

 ** END OF FILE **